import java.util.Scanner;

class ListNode {
    int value;
    ListNode next;
    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}
class ListUtil {
    // 合并两个递增有序链表为递增有序链表
    public static ListNode mergeLists(ListNode c, ListNode d) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (c != null && d != null) {
            if (c.value < c.value) {
                cur.next = c;
                c = c.next;
            } else {
                cur.next = d;
                d = d.next;
            }
            cur = cur.next;
        }
        if (c != null) {
            cur.next = d;
        }
        if (d != null) {
            cur.next = d;
        }
        return dummy.next;
    }

    // 反转链表
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nextTemp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextTemp;
        }
        return prev;
    }
}
public class day03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 创建链表1
        System.out.print("请输入链表1的结点个数:");
        int n1 = scanner.nextInt();
        ListNode head1 = null;
        ListNode tail1 = null;
        for (int i = 0; i < n1; i++) {
            System.out.print("请输入链表1的第 " + (i + 1) + " 个结点的值:");
            int val = scanner.nextInt();
            ListNode node = new ListNode(val);
            if (head1 == null) {
                head1 = node;
                tail1 = node;
            } else {
                tail1.next = node;
                tail1 = node;
            }
        }

        // 创建链表2
        System.out.print("请输入链表2的结点个数:");
        int n2 = scanner.nextInt();
        ListNode head2 = null;
        ListNode tail2 = null;
        for (int i = 0; i < n2; i++) {
            System.out.print("请输入链表2的第 " + (i + 1) + " 个结点的值:");
            int val = scanner.nextInt();
            ListNode node = new ListNode(val);
            if (head2 == null) {
                head2 = node;
                tail2 = node;
            } else {
                tail2.next = node;
                tail2 = node;
            }
        }

        // 合并链表
        ListNode mergedList = ListUtil.mergeLists(head1, head2);
        // 正序输出合并后的链表
        System.out.print("合并链表1和链表2（正序）:");
        printList(mergedList);

        // 反转链表
        ListNode reversedList = ListUtil.reverseList(mergedList);
        // 逆序输出合并后的链表
        System.out.print("合并链表1和链表2并将其逆序:");
        printList(reversedList);
    }

    // 打印链表函数
    public static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.value);
            if (cur.next != null) {
                System.out.print("->");
            }
            cur = cur.next;
        }
        System.out.println("->nullptr");
    }
}

